1. Field of Invention
This invention pertains to method and apparatus for correcting errors occurring in digital data.
2. Related Art and Other Considerations
In a digital data communication system (including storage and retrieval from optical or rotating magnetic media), error control systems are typically employed to increase the transfer rate of information and at the same time make the error rate arbitrarily low. For fixed signal-to-noise ratios and fixed bandwidths improvements can be made through the use of error-correcting codes (ECC).
With error-correction coding, the data to be transmitted or stored is mathematically processed through appropriate circuitry and/or software to obtain additional data symbols called check symbols or redundancy symbols. For further reliable communications it is necessary to be reasonably sure of detecting all transmission errors. One way of doing this is by the use of cyclic redundancy check symbols or CRCs. In general CRCs are calculated by treating data as the coefficients of a polynomial, dividing the data by another polynomial, and keeping the remainder.
The data bytes, CRC bytes, and ECC bytes together make up a codeword. The data bytes are the first bytes in the codeword. The CRC bytes follow the data bytes. The ECC bytes follow the CRC bytes. C(x) is defined as: ##EQU1## where CR.sub.n are the CRC bytes, D.sub.n are the data bytes, E.sub.n are the ECC bytes, s is the number of data bytes and m is the number of CRC bytes. Prior art error correction systems employ either bit-oriented or symbol-oriented CRC. However, the disadvantage of such systems is that each one is most desirable for various expected errors. That is, a bit-oriented CRC is desired if the expected errors are random bit errors whereas a symbol-oriented CRC is desired if the expected errors are burst errors or random symbol errors.
Moreover, in some magnetic disk applications, such as the writing and reading of ID fields in the header portion of a formatted sector necessitate the use of codes which can quickly correct short bursts in a small block of data on-the-fly. As existing prior art error correction systems do not correct errors located in the header ID field, such a capability is clearly needed to ensure correctly locating formatted sectors.
Additionally, all known implementations of decoding Reed-Solomon codes (a class of multiple-error correcting codes) using the Berlekamp-Massey algorithm for generating the error locator polynomial need temporary storage for at least storing the error locator polynomial coefficient resulting in an inefficient and unnecessary system costs.
While the use of ECC and CRC lower the overall probability of transferring undetected erroneous data, neither one ensures the transfer of a correct sector from the storage media to the host. Therefore, the need arises to ensure the integrity of such a transfer.
Prior art solutions generally employ a one-codeword buffer or storage means to implement on-the-fly multi-error correction system. Correction on data read from the disk is performed as data leaves a buffer local to the ECC and is corrected while in the local buffer. The corrected data is then stored in a larger buffer storing multiple codewords. The disadvantage of these system is the need for multiple buffers.
Thus, the need arises for an error tolerant system to ensure the integrity of transfer of information while maintaining efficiency.